41. First Missing Positive
Hard

Given an unsorted integer array nums, find the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

 

Example 1:

Input: nums = [1,2,0]
Output: 3

Example 2:

Input: nums = [3,4,-1,1]
Output: 2

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1

 

Constraints:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1
Accepted
498.8K
Submissions
1.4M
Seen this question in a real interview before?
Related Topics
Show Hint 1
Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
Show Hint 2
We don't care about duplicates or non-positive integers
Show Hint 3
Remember that O(2n) = O(n)

Average Rating: 3.65 (108 votes)

Premium

Solution


Approach 1: Index as a hash key.

Data clean up

First of all let's get rid of negative numbers and zeros since there is no need of them. One could get rid of all numbers larger than n as well, since the first missing positive is for sure smaller or equal to n + 1. The case when the first missing positive is equal to n + 1 will be treated separately.

max_first

What does it mean - to get rid of, if one has to keep O(N)\mathcal{O}(N) time complexity and hence could not pop unwanted elements out? Let's just replace all these by 1s.

max_first

To ensure that the first missing positive is not 1, one has to verify the presence of 1 before proceeding to this operation.

How to solve in-place

Now there we have an array which contains only positive numbers in a range from 1 to n, and the problem is to find a first missing positive in O(N)\mathcal{O}(N) time and constant space.

That would be simple, if one would be allowed to have a hash-map positive number -> its presence for the array.

max_first

Sort of "dirty workaround" solution would be to allocate a string hash_str with n zeros, and use it as a sort of hash map by changing hash_str[i] to 1 each time one meets number i in the array.

max_first

Let's not use this solution, but just take away a pretty nice idea to use index as a hash-key for a positive number.

The final idea is to use index in nums as a hash key and sign of the element as a hash value which is presence detector.

For example, negative sign of nums[2] element means that number 2 is present in nums. The positive sign of nums[3] element means that number 3 is not present (missing) in nums.

To achieve that let's walk along the array (which after clean up contains only positive numbers), check each element value elem and change the sign of element nums[elem] to negative to mark that number elem is present in nums. Be careful with duplicates and ensure that the sign was changed only once.

max_first

Algorithm

Now everything is ready to write down the algorithm.

  • Check if 1 is present in the array. If not, you're done and 1 is the answer.
  • Replace negative numbers, zeros, and numbers larger than n by 1s.
  • Walk along the array. Change the sign of a-th element if you meet number a. Be careful with duplicates : do sign change only once. Use index 0 to save an information about presence of number n since index n is not available.
  • Walk again along the array. Return the index of the first positive element.
  • If nums[0] > 0 return n.
  • If on the previous step you didn't find the positive element in nums, that means that the answer is n + 1.

Implementation

Current
1 / 4

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) since all we do here is four walks along the array of length N.
  • Space complexity : O(1)\mathcal{O}(1) since this is a constant space solution.

Report Article Issue

Comments: 89
Haomin0817's avatar
Read More

Another O(n) solution use cycle sort:

def firstMissingPositive(self, nums: List[int]) -> int:
    i = 0
    n = len(nums)
    while i < n:
        j = nums[i] - 1
        # put num[i] to the correct place if nums[i] in the range [1, n]
        if 0 <= j < n and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    # so far, all the integers that could find their own correct place 
    # have been put to the correct place, next thing is to find out the
    # place that occupied wrongly
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

103
Show 4 replies
Reply
Share
Report
karbayev's avatar
Read More

Solution with a string of length of n is not O(1) space complexity, it's O(n)

92
Show 3 replies
Reply
Share
Report
parag_meshram's avatar
Read More

The problem should specify that it is ok if you alter the existing array because to my surprise the LeetCode solution doesn't care about modifying the existing array.

31
Show 4 replies
Reply
Share
Report
coder_xyzzy's avatar
Read More

Nice solution, but it's possible to do this in one pass, considering each value at most twice, and not destroying the contents of the array (though changing its order).

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // We will partition the array into two sides, with one copy of each number
        // on the left, in order, as far as possible.
        // [1, 2, 3, 4, 5, ..., n][...(everything else, but not n+1)...].
        int i = 0, end = nums.size();
        // Call LeftPartition the interval [1, ..., i - 1]
        // Call RightPartition the interval [nums[end], nums[nums.size() - 1]].
        // Initially, both are empty.
        // At the end, when "i" and "end" meet, call the results FinalLeftPartition and FinalRightPartition.
        // Then the answer to the problem is 1 + size(FinalLeftPartition).
        //
        // We build those intervals in-place, by swapping elements when necessary, and updating i and end.
        while (i != end) {
            int val = nums[i];
            if (val == 1 + i) // Number is in the right place. We may consider it part of LeftPartition, and advance i.
                ++i;
            else if (
                val > end // If this should go in FinalLeftPartition, then that would overlap with FinalRightPartition.
                || val <= 0 // The number is negative, it cannot possibly belong in FinalLeftPartition.
                || nums[val - 1] == val // This is a duplicate. It doesn't belong in FinalLeftPartition.
                    // How can we get away with checking just this one spot for a duplicate?
                    // See the next "else" branch -- we always put values into this exact spot.
            ) {
                // If any of the above statements is true, this value doesn't need to be in FinalLeftPartition.
                // So we may put it in the right partition,
                // and advance "end".
                swap(nums[i], nums[--end]);
                // Now nums[i] has some new value that we haven't considered before, so
                // leave "i" as is and go back to the top of the loop.
            } else {
                // We don't yet know whether val should be in
                // FinalLeftPartition or FinalRightPartition, so put it in neither.
                // In order to consider another value, place val so that it matches its own index;
                // that is, place it where it will be if indeed it ends up in FinalLeftPartition,
                // and next consider the element there.
                swap(nums[i], nums[val - 1]);
                // We learned nothing new about what elements will be in FinalLeftPartition or FinalRightPartition,
                // and nums[i] has the previous value of nums[val - i], which we haven't dealt with yet,
                // so continue the loop without advancing either pointer.
                // But we did make useful progress in this branch: now in the future, if we see the same "val"
                // again, we will know it's a duplicate, because of the "nums[val - 1] == val" check above!
            }
        }
        return i + 1;
    }
};

49
Show 10 replies
Reply
Share
Report
totsubo's avatar
Read More

One could get rid of all numbers larger than n as well, since the first missing positive is for sure smaller or equal to n + 1

This isn't obvious and could use some more explanation.

I find solutions that just state something without proving it to be especially annoying.

I tried to give an explanation here:

https://leetcode.com/problems/first-missing-positive/discuss/319270/Explanation-of-crucial-observation-needed-to-deduce-algorithm

18
Show 4 replies
Reply
Share
Report
nickyflash's avatar
Read More

This doesn't really count as O(1) because it relies on destructively modifying the input, and in almost any real life use case, you never want your functions to modify the input data.

32
Show 2 replies
Reply
Share
Report
nqm149's avatar
Read More

we can apply cyclic replacement which cost O(n) to swap and put all numbers in their correct positions in array

class Solution {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i ++){
            int curr = nums[i];
            // curr-1 is the next index to swap and must be inside bound
            while (curr-1 >= 0 && curr-1 < nums.length && nums[curr - 1] != curr){
                int temp = nums[curr - 1];
                nums[curr - 1] = curr;
                curr = temp;
            }
        }
        for (int i = 0; i < nums.length; i ++){
            if (nums[i] != i + 1) return i + 1;
        }
        return nums.length + 1;
    }
}    

10
Show 4 replies
Reply
Share
Report
manchesterunited's avatar
Read More

Should the following statement:
If array contains only one element and it's not 1, the answer is 2.
be:
If array contains only one element and it's 1, the answer is 2.
?

4
Show 2 replies
Reply
Share
Report
yushey's avatar
Read More

just use a heap..

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        heapq.heapify(nums)
        num = 1
        for i in range(len(nums)):
            x = heapq.heappop(nums)
            if (x > 0 and x==num):
                num+=1
        return num

3
Show 4 replies
Reply
Share
Report
manchesterunited's avatar
Read More

And ArrayIndexOutOfBoundsException while processing {1,3,3};

Should:
else if (nums[a] > 0)
nums[a] *= -1;
be changed to:
else if (a != n && nums[a] > 0)
nums[a] *= -1;
?

3
Show 4 replies
Reply
Share
Report
Success
Details
Runtime: 100 ms, faster than 61.36% of C++ online submissions for First Missing Positive.
Memory Usage: 66.1 MB, less than 41.94% of C++ online submissions for First Missing Positive.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/15/2021 08:12Accepted100 ms66.1 MBcpp
07/28/2020 19:13Accepted4 ms9.8 MBcpp
07/28/2020 19:11Wrong AnswerN/AN/Acpp
07/28/2020 19:11Wrong AnswerN/AN/Acpp
05/02/2020 20:01Accepted0 ms10.1 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.